package meituan;

import com.sun.deploy.util.StringUtils;
import org.junit.Test;

import java.util.*;

/**
 * @Description 无重复字符的最长子串:哈希、滑动窗口
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * @Author luozhenting
 * @Date 2021/10/13
 **/
public class LengthOfLongestSubstring {

    public int lengthOfLongestSubstring2(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                start = Math.max(map.get(ch) + 1, start);
            }
            max = Math.max(max, end - start + 1);
            map.put(ch, end);
        }
        return max;
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }
        int start = 0;
        int end = 0;
        int startNow = 0;
        int endNow = 0;
        Queue<Character> queue = new LinkedList<>();
        Map<Character, Integer> charsHash = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                charsHash.put(s.charAt(i), i);
                queue.offer(s.charAt(i));
                continue;
            }
            if (charsHash.getOrDefault(s.charAt(i), null) == null) {
                charsHash.put(s.charAt(i), i);
                queue.offer(s.charAt(i));
                endNow += 1;
                if (end - start < endNow - startNow) {
                    start = startNow;
                    end = endNow;
                }
            } else {
                while (!queue.isEmpty()) {
                    char c = queue.poll();
                    charsHash.remove(c);
                    if (c == s.charAt(i)) {
                        charsHash.put(c, i);
                        queue.offer(c);
                        break;
                    }
                }
                startNow = queue.isEmpty() ? i : charsHash.get(queue.peek());
                endNow = charsHash.get(s.charAt(i));
            }
        }

        return end - start + 1;
    }

    @Test
    public void myTest() {
        System.out.println(this.lengthOfLongestSubstring("cdd"));
    }
}
